﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
using Boomer.Source.Character;
using Boomer.Source.FrameWork;
using Boomer.Source.TiledMap;

namespace Boomer.Source.PathFinding
{
    class CPathFinding
    {
        int tempt;
        public Vector2 posNext;
        public static Vector2 goalPos = new Vector2();
        int VOCUC = 9999;
        int[,] L = new int[100, 100];
        int[,] matrixgame = new int[10, 10];
        int[] BelongT = new int[100];
        int[] Prev = new int[100];
        int[] Length = new int[100];
        int[,] indexMatrix = new int[10, 10]	   
                                                     {	{ 0, 10, 20 , 30 , 40 , 50 , 60 , 70 , 80 , 90  }, 
										                { 1, 11, 21 , 31 , 41 , 51 , 61 , 71 , 81 , 91} , 
										                { 2, 12, 22 , 32 , 42 , 52 , 62 , 72 , 82 , 92} ,
										                { 3, 13, 23 , 33 , 43 , 53 , 63 , 73 , 83 , 93} ,
										                { 4, 14, 24 , 34 , 44 , 54 , 64 , 74 , 84 , 94} ,
										                { 5, 15, 25 , 35 , 45 , 55 , 65 , 75 , 85 , 95} ,
										                { 6, 16, 26 , 36 , 46 , 56 , 66 , 76 , 86 , 96} ,
										                { 7, 17, 27 , 37 , 47 , 57 , 67 , 77 , 87 , 97} ,
										                { 8, 18, 28 , 38 , 48 , 58 , 68 , 78 , 88 , 98} ,
										                { 9, 19, 29 , 39 , 49 , 59 , 69 , 79 , 89 , 99} };

        public CPathFinding(CTiledMap map)
        {
            int i, j;
            for (i = 0; i < map.m_iMapHeight; i++)
            {
                for (j = 0; j < map.m_iMapWidth; j++)
                {
                    matrixgame[i, j] = map.getCell(i, j);

                }
            }
            for (i = 0; i < map.m_iMapHeight; i++)
            {
                for (j = 0; j < map.m_iMapWidth; j++)
                {
                    if (matrixgame[i, j] == 9)
                    {
                        if (i - 1 >= 0 && matrixgame[i - 1, j] == 0)
                        {
                            matrixgame[i - 1, j] = 100;
                        }
                        if (i + 1 <= 9 && matrixgame[i + 1, j] == 0)
                        {
                            matrixgame[i + 1, j] = 100;
                        }
                        if (j - 1 >= 0 && matrixgame[i, j - 1] == 0)
                        {
                            matrixgame[i, j - 1] = 100;
                        }
                        if (j + 1 <= 9 && matrixgame[i, j + 1] == 0)
                        {
                            matrixgame[i, j + 1] = 100;
                        }
                    }

                }
            }

            for (i = 0; i < map.m_iMapHeight; i++)
            {
                for (j = 0; j < map.m_iMapWidth; j++)
                {
                    if (matrixgame[i, j] == 0 || matrixgame[i, j] == 9 || matrixgame[i, j] == 100)
                    {
                        if ((i - 1) >= 0 && matrixgame[i - 1, j] == 0)
                        {
                            L[indexMatrix[i, j], indexMatrix[i - 1, j]] = 1;
                            L[indexMatrix[i - 1, j], indexMatrix[i, j]] = 1;
                        }
                        if ((i + 1) <= 9 && matrixgame[i + 1, j] == 0)
                        {
                            L[indexMatrix[i, j], indexMatrix[i + 1, j]] = 1;
                            L[indexMatrix[i + 1, j], indexMatrix[i, j]] = 1;
                        }
                        if ((j - 1) >= 0 && matrixgame[i, j - 1] == 0)
                        {
                            L[indexMatrix[i, j - 1], indexMatrix[i, j]] = 1;
                            L[indexMatrix[i, j], indexMatrix[i, j - 1]] = 1;
                        }
                        if ((j + 1) <= 9 && matrixgame[i, j + 1] == 0)
                        {
                            L[indexMatrix[i, j + 1], indexMatrix[i, j]] = 1;
                            L[indexMatrix[i, j], indexMatrix[i, j + 1]] = 1;
                        }
                    }
                }
            }
        }

        void Init_Dijkstra(int start)
        {
            for (int i = 0; i < 100; i++)
            {
                BelongT[i] = 1;
                Prev[i] = -1;
                Length[i] = VOCUC;
            }
            Length[start] = 0;
        }

        int conver(Vector2 mapIndex)
        {
            return indexMatrix[(int)mapIndex.X, (int)mapIndex.Y];
        }

        public int Dijkstra_Alg(Vector2 startPos, Vector2 goalPos)
        {
            CPathFinding.goalPos = goalPos;
            int start = conver(startPos);
            int goal = conver(goalPos);
            Init_Dijkstra(start);
            while (BelongT[goal] == 1)
            {
                int min = VOCUC;
                int v = -1;
                //Tim min thuoc T:
                for (int i = 0; i < 100; i++)
                {
                    if (BelongT[i] == 1)
                    {
                        if (min > Length[i])
                        {
                            min = Length[i];
                            v = i;
                        }
                    }
                }
                //Loai v ra khoi T:
                if (v == -1)
                    return -1;
                BelongT[v] = 0;

                for (int k = 0; k < 100; k++)
                {
                    if (BelongT[k] != 0 && L[v, k] != 0)
                    {
                        if (Length[k] > Length[v] + L[v, k])
                        {
                            Length[k] = Length[v] + L[v, k];
                            Prev[k] = v;
                        }
                        else
                            if (Length[k] > Length[v] + L[k, v])
                            {
                                Length[k] = Length[v] + L[k, v];
                                Prev[k] = v;
                            }
                    }
                }
            }
            int cost = 0;
            if (Prev[goal] == -1)
            {
                posNext = CPathFinding.goalPos;
                return 1;
            }
            else
            {
                cost = L[Prev[goal], goal];
                tempt = 0;
                while (goal != start)
                {
                    tempt = goal;
                    goal = Prev[goal];
                    if (Prev[goal] == -1)
                    {
                        break;
                    }
                }
            }
            for (int i = 0; i < 10; i++)
            {
                for (int j = 0; j < 10; j++)
                {
                    if (indexMatrix[i, j] == tempt)
                    {
                        posNext = new Vector2(i, j);
                    }
                }
            }

            return 0;
            // tra ve buoc di tip theo

        }
    }
}
